package 优先算法.滑动窗口.串联所有单词的子串;

import java.util.*;



public class Main {
    public static void main(String[] args) {
        String s = "aaaaaaaaaaaaaa";
        String[] words = {"aa","aa"};
        Solution so = new Solution();
        List<Integer> rel = so.findSubstring(s, words);
        System.out.println(rel);
    }
}
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        HashMap<String,Integer> hash2 = new HashMap<>();
        HashMap<String,Integer> hash1 = new HashMap<>();
        for (String word : words){
            hash1.put(word,hash1.getOrDefault(word,0)+1);
        }
        int len = words[0].length();
        int All = words.length;


        //循环计数器 countWhile
        int countWhile = 0;
        while(countWhile < len){
            String[] charArray =splitString(s,len,countWhile);
            int left = 0,right = 0,count = 0;
            while(right < charArray.length){
                //进窗口
                String in =charArray[right];
                hash2.put(in,hash2.getOrDefault(in, 0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in, 0)){
                    count++;
                }
                right++;
                if(right-left > All){
                    int out = hash2.get(charArray[left]);
                    if(hash2.get(charArray[left]) <= hash1.getOrDefault(charArray[left], 0)){
                        count--;
                    }
                    hash2.put(charArray[left],--out);
                    left++;
                }

                if(count == All ){
                    result.add(left*len+countWhile);
                }
            }
            hash2.clear();
            countWhile++;
        }
        return result;
    }
    public static String[] splitString(String input, int chunkSize, int startPosition) {
        int length = input.length() - startPosition;
        int numOfChunks = (int) Math.ceil((double) length / chunkSize);

        String[] result = new String[numOfChunks];

        for (int i = 0; i < numOfChunks; i++) {
            int start = startPosition + i * chunkSize;
            int end = Math.min(start + chunkSize, length + startPosition);
            result[i] = input.substring(start, end);
        }

        return result;
    }
}